\documentclass[submission]{FPSAC2017}

\articlenumber{79}
\addbibresource{79_Chapuy.bib}

\usepackage{enumitem}
\usepackage{comment}


\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conjecture}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{rem}{Remark}

\newcommand{\Aut}{\text{Aut}}
\renewcommand{\deg}{\text{deg}}

\newcommand{\cE}{\mathcal{E}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\qq}{\mathbf{q}}
\newcommand{\vv}{\mathbf{v}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\sst}{\mathbf{s}}
\newcommand{\ee}{\mathbf{e}}
\newcommand{\XX}{\mathbf{X}}
\newcommand{\YY}{\mathbf{Y}}
\newcommand{\subscript}[2]{$#1 _ #2$}
\newcommand{\qginf}{\qq_\infty^{(g)}}
\newcommand{\qgn}{\qq_{n}^{(g)}}
\newcommand{\QQgn}{\mathcal{Q}_n^{(g)}}
\newcommand{\pnalpha}{p_{n,\alpha}}
\usepackage{lipsum}

\title[Tessellations and $t_g$-recurrence]{On tessellations of random maps and the $t_g$-recurrence}

\author{Guillaume Chapuy%
\thanks{
	Support from the European Research Council, grant ERC-2016-STG 716083 ``CombiTop'', from the City of Paris, grant ``\'Emergences, Combinatoire \`a Paris'', and from the grant ANR~12-JS02-001-01 ``Cartaplus''.
}
}
\address{IRIF (ex-LIAFA), UMR CNRS 8243,
Universit\'e Paris-Diderot,
France}



\received{\today}


\newcommand{\abss}{The number of $n$-edge embedded graphs (rooted maps) on the $g$-torus grows as $t_gn^{5(g-1)/2}12^n$ when $n$ tends to infinity. The constants $t_g$ can be computed via the non-linear ``$t_g$-recurrence'', strongly related to the KP hierarchy and the double scaling limit of the one-matrix model. The combinatorial meaning of this simple recurrence is still mysterious, and the purpose of this work is to point out an interpretation via  random maps on surfaces. 
Namely, we show  that the $t_g$-recurrence  is equivalent, via combinatorial bijections, to the fact that $\mathbf{E}X_g^2=\frac{1}{3}$ for any $g\geq 0$, where $X_g,1-X_g$ are the masses of the nearest-neighbour cells surrounding two randomly chosen points in a Brownian map of genus $g$. 
This raises the question (that we leave open) of giving an independent probabilistic or combinatorial derivation of this second moment, which would lead to a fully concrete proof of the $t_g$-recurrence.
In fact, we conjecture that for any $g\geq 0$ and $k\geq 2$, the masses of the $k$ nearest-neighbour cells induced by $k$ uniform points in the genus $g$ Brownian map form a uniform $k$-division of the unit interval. We leave this question open even for $(g,k)=(0,2)$.
}



\abstract{\abss}

\resume{Le nombre de graphes plong\'es \`{a} $n$ ar\^etes (cartes enracin\'ees) sur le $g$-tore cro\^{\i}t comme $t_gn^{5(g-1)/2}12^n$ quand $n\rightarrow\infty$. Les constantes $t_g$ peuvent \^etre calcul\'ees gr\^ace \`{a}  la r\'ecurrence-$t_g$, non lin\'eaire, fortement li\'ee \`a la hi\'erarchie KP et \`a la double limit d'\'echelle du mod\`ele \`a une matrice. Le sens combinatoire de cette r\'ecurrence simple demeure myst\'erieux, et le but de ce travail est d'en fournir une interpr\'etation via les cartes al\'eatoires. 
\`A savoir, nous montrons que la r\'ecurrence-$t_g$ est \'equivalente, via des bijections combinatoires, au fait que $\mathbf{E}X_g^2=\frac{1}{3}$ pour tout $g\geq 0$, o\`u $X_g,1-X_g$ sont les masses des cellules des plus proches voisins entourant deux points choisis au hasard dans une carte brownienne de genre $g$.
Cela soul\`eve la question (que nous laissons ouverte) de donner une d\'erivation probabiliste ou combinatoire ind\'ependante de ce second moment, ce qui conduirait \`A une d\'emonstration concr\`ete compl\`ete de la r\'ecurrence-$t_g$.
En fait, on conjecture que pour tout $g\geq 0$ et $k\geq 2$, les masses des $k$ cellules des plus proches voisins induites par $k$ points uniformes dans la carte brownienne de genre $g$ forment une $k$-division uniforme de l'intervale $[0,1]$. On laisse cette question ouverte m\^eme pour $(g,k)=(0,2)$.}

\keywords{Maps on surfaces, bijections, asymptotic enumeration, KP hierarchy}




\begin{document}

\maketitle

\section{Introduction and results}


In this note a \emph{map} is a graph embedded without edge crossings on a closed oriented surface, in such a way that the connected components of the complement of the graph, called \emph{faces}, are all homeomorphic to a disk. Loops and multiple edges are allowed, and maps are considered up to oriented homeomorphisms. A map is \emph{rooted} if one edge is distinguished and oriented. The number $m_g(n)$ of rooted maps with $n$ edges on the surface of genus $g$ satisfies, for fixed $g\geq 0$ and $n\rightarrow \infty$:
\begin{eqnarray}\label{eq:mgn}
m_g(n) \sim t_g n^{\frac{5(g-1)}{2}} 12^n, \mbox{ for }t_g >0.
\end{eqnarray}
In genus $0$, this result follows from the exact formula $m_0(n)=\frac{2\cdot 3^n}{(n+2)(n+1)}{2n \choose n}$ due to Tutte~\cite{Tutte:census}. In higher genus, it was proved by Bender and Canfield in~\cite{BC0}.
A direct combinatorial interpretation of the genus $0$ formula was given by Cori and Vauquelin~\cite{CV} and much simplified by Schaeffer~\cite{Schaeffer:PhD,ChassaingSchaeffer}. A combinatorial interpretation of~\eqref{eq:mgn} was given in~\cite{CMS} using the Marcus-Schaeffer bijection~\cite{MS} and further developed in~\cite{Chapuy:trisections}.

None of the methods just mentioned enable us to say much about the sequence of constants $(t_g)_{g\geq 0}$ that appear in~\eqref{eq:mgn}, and indeed these references give explicit values only for very small values of~$g$. There is however a remarkable recurrence formula to compute these numbers, that we call the \emph{$t_g$-recurrence}. It is better expressed in terms of the numbers $\tau_g=2^{5g-2}\Gamma\left(\frac{5g-1}{2}\right)t_g$ and is given by:
\begin{eqnarray}\label{eq:tg}
\tau_{g+1} = \frac{(5g+1)(5g-1)}{3}\tau_{g}+\tfrac{1}{2}\sum_{g_1=1}^{g}\tau_{g_1}\tau_{g+1-g_1}, \ \ g \geq 0,
\end{eqnarray}
which enables us to compute these numbers easily starting from $\tau_0=-1$. This result was first stated in mathematical physics in relation with the \emph{double scaling limit} of the one-matrix model, and  obtained via a non-rigorous scaling of expressions involving orthogonal polynomials  (we refer to~\cite[p201]{LZ} for historical references). A more algebraic  approach is based on the fact that the partition function of maps on surfaces, with infinitely many parameters marking vertex degrees, is a tau-function of the KP hierarchy. Going from the KP hierarchy to the recurrence \eqref{eq:tg} (or to an equivalent Painlev\'{e}-I ODE for an associated generating function) relies on a trick of elimination of variables that can be performed in different ways and whose generality is, as far as we know, yet to be fully understood (for the case of triangulations see \cite[Appendix B.]{mcfly} or \cite{GJ, tg} and for general maps see~\cite{CC}).



The main observation of this note is to relate the recurrence \eqref{eq:tg} to another side of the story, namely the study of random maps and their scaling limits. We refer to the introductions of the papers~\cite{Miermont:tessellations, Miermont:GH,LG:GH} for an introduction to the topic and for references.
To state our main observation we first need a few more definitions. A \emph{quadrangulation} is a map in which each face contains exactly four corners, {\it i.e.} is bordered by exactly four edge-sides. It is \emph{bipartite} if its vertices can be colored in black and white in such a way that there is no monochromatic edge.
 For each $n,g\geq0$, there is a classical bijection, due to Tutte, between rooted maps of genus $g$ with $n$ edges and rooted bipartite quadrangulations of genus $g$ with $n$ faces.

For $n,g\geq 0$, we let $\QQgn$ be the set of rooted bipartite quadrangulations of genus $g$ with $n$ faces (with the convention that there is a single quadrangulation with $0$ faces, which has genus $0$, no edges, and two vertices). We let $\qgn \in_u \QQgn$ be a bipartite quadrangulation of genus $g$ with $n$ faces chosen uniformly at random. We equip the vertex set of $\qgn$ with the graph distance, noted $\mathbf{d}_n$, and with the uniform measure, noted ${\mu}_n$. This makes $\qgn\equiv (\qgn,\mathbf{d}_n,\mu_n)$ into a compact measured metric space. The set of (isometry classes of) such spaces is equipped with the Gromov-Hausdorff-Prokhorov (GHP) topology as in~\cite[Sec.~6]{Miermont:tessellations}. 
A \emph{Brownian map of genus $g$} is a random compact measured metric space $(\qq_\infty, d_\infty, \mu_\infty)$ that is such that:
$$
(\qgn,\tfrac{1}{n^{1/4}}\mathbf{d}_n,\mu_n)
\longrightarrow
(\qginf, d_\infty, \mu_\infty),
$$
in distribution along some subsequence for the GHP topology. The existence of Brownian maps of genus $g$ was proved in~\cite{Miermont:tessellations}, and their uniqueness for each $g \geq 1$ has been announced by Bettinelli and Miermont~\cite{BettinelliMiermont} (in genus $0$ the uniqueness is an important result proved independently by Miermont~\cite{Miermont:GH} and Le Gall~\cite{LG:GH}). However the uniqueness of the limit is not needed for our discussion since we will prove the convergence of all the observables we are interested in.

\begingroup\emergencystretch=3em
\begin{thm}[First observation, obtained by combinatorial means]\label{thm:obs1}
For $g\geq 0$,  let $(\qginf, d_\infty, \mu_\infty)$ be a Brownian map of genus $g$. Let $\vv_1,\vv_2 \in \qq^{(g)}_\infty$ be chosen independently according to the probability  measure $\mu_\infty$, and let $\XX_g, 1-\XX_g$ be the masses of the corresponding cells in the nearest neighbour tessellation of $\qginf$ induced by $\vv_1$ and $\vv_2$, that is to say:
$$
\XX_g := \mu_\infty\Big(\big\{x\in \qginf,\ d_\infty(x,\vv_1)<d_\infty(x,\vv_2) \big\}\Big).
$$
 Then the sequence of numbers $\tau_g=2^{5g-2}\Gamma\left(\frac{5g-1}{2}\right)t_g$ satisfies:
$$
\tau_{g+1} =  2(5g+1)(5g-1)\tau_{g}\cdot \mathbf{E}[\XX_{g}(1-\XX_g)] 
+\frac{1}{2}\sum_{g_1=1}^{g}\tau_{g_1}\tau_{g+1-g_1}, \ \ \ g\geq 0.
$$
\end{thm}
\endgroup

From~\eqref{eq:tg} we immediately deduce:
\begin{thm}[Second observation, by comparing \cref{thm:obs1} with the $t_g$-recurrence~\eqref{eq:tg}] \label{cor:main}
For any $g\geq 0$, the random variable $\XX_g$ satisfies
	$$\mathbf{E}[\XX_g(1-\XX_g)]=\frac{1}{6}, \, \, \mbox{ or equivalently }
 \mathbf{E}\XX_g^2=\frac{1}{3}.$$
\end{thm}
The reader may be surprised that $\mathbf{E}\XX_g^2$ does not depend on $g\geq0$: indeed, although it is natural to expect that \emph{local} statistics of Brownian maps do not depend on the genus,  the nearest-neighbour tessellation depends \emph{globally}  of the metric space $\qginf$, which \emph{is} genus dependent. This unexpected property  suggests that there exists a simple probabilistic or combinatorial interpretation of this mysterious fact, based on a symmetry of the Brownian map, but we have not been able to find it. 
We emphasize that, via \cref{thm:obs1}, such an interpretation would provide  a proof of the $t_g$-recurrence independent of orthogonal polynomials, matrix models or integrable hierarchies.


It is natural to ask if other moments of the variables $\XX_g$ or related random variables are computable, and in what way they depend on the genus. Unfortunately we will not go very far in this direction. Let $\vv_1,\vv_2,\dots,\vv_k$ be $k\geq 2$ points in $\qginf$ chosen independently at random according to the Lebesgue measure $\mu_\infty$. Let $(\YY_g^{(i:k)})_{1\leq i \leq k}$ be the masses of the $k$-nearest-neighbour cells induced by the $\vv_i$'s,
\textit{i.e.} for $i\in[1..k]$ let 
$$\YY_g^{(i:k)}:=\mu_\infty \Big(\big\{ x\in \qginf, \ \forall j\in [1..k]\setminus\{i\}, \ d_\infty(x,\vv_i)<d_\infty(x,\vv_j)\big\}\Big).$$
We note that $\XX_g=\YY_g^{(1:2)}$, 
 but we prefer to keep the lighter notation $\XX_g$ for $\YY_g^{(1:2)}$ throughout this note. 
The following result is similar to, and as mysterious as \cref{cor:main}:
\begin{thm}[A similar simple formula for the case of three points]\label{thm:3points}
For $g\geq 0$, the masses $\YY_g^{(1:3)}, \YY_g^{(2:3)}, \YY_g^{(3:3)}$ of the Vorono\"i cells induced by three independent Lebesgue distributed points in the Brownian map of genus $g$ satisfy, for $g\geq 0$:
$$
\mathbf{E}[\YY_g^{(1:3)}\YY_g^{(2:3)}\YY_g^{(3:3)}] 
=\frac{1}{60}.
$$
\end{thm}
As we will see, the fact that this moment is computable reflects the existence of a combinatorial device  known as the ``trisection lemma''~\cite{Chapuy:trisections}. The fact that it does not depend on the genus, and that it coincides\footnote{If $U_1,U_2$ are two independent uniforms on $[0,1]$ and $I_1, I_2, I_3$ are the lengths of the three intervals they define, then 
$\mathbf{E} (I_1I_2I_3)$  is the probability that five independent uniforms $U_1,U_2,V_1,V_2,V_3$ are ordered as $V_1<U_{1}\wedge U_2<V_2<U_1\vee U_{2}<V_3$, which is clearly equal to $\frac{2}{5!}=\tfrac{1}{60}$.} with the corresponding moment for a uniform three-division of the interval $[0,1]$, is as mysterious as for the previous result (or even more, since the computations leading to \cref{thm:3points} are quite delicate).


 We won't prove anything on higher moments or other values of~$k$ since we lack the tools to study them. However, numerical simulations suggest the remarkable property:
\begin{conjecture}\label{conjecture}
For $k\geq 2, g\geq 0$, let $\qginf \equiv (\qginf, d_\infty, \mu_\infty)$ be a genus $g$ Brownian map and let $\vv_1,\dots,\vv_k$ be chosen according to $\mu_\infty^{\otimes k}$. Then the random vector $(\YY_g^{(1:k)},\YY_g^{(2:k)},\dots, \YY_g^{(k:k)})$ has the same law as the subdivision of the unit interval induced by $k-1$ independent uniform variables. In particular, for any $g\geq 0$, $\XX_g=\YY_g^{(1:2)}$ is uniform on $[0,1]$.
\end{conjecture}

To conclude this introduction, we emphasize that our main observation relates the moment $\mathbf{E}\XX_g^2$ to the $g$-th step of the $t_g$-recurrence. In particular, the fact that  $\mathbf{E}\XX_0^2=1/3$ for the \emph{genus~$0$} Brownian map is only ``equivalent'' to the computation of the genus $1$ constant $t_1$, which can be performed by hand in several ways (and similarly, our proof of \cref{thm:3points} for $g=0$ relies only on the value of the constants $t_1$ and $t_2$).
However, proving \cref{conjecture} even for $(g,k)=(0,2)$ would be interesting in itself. Readers familiar with Miermont's bijection~\cite{Miermont:tessellations} may try to approach this problem by exact counting of well-labelled 2-face maps (we have failed trying to do so). One could also hope that in the future purely probabilistic methods (for example using the QLE viewpoint on the Brownian map~\cite{MillerSheffield}) will enable to determine the full law of~$\XX_0$ or even the law of the vector $(\YY_0^{(i:k)})_{1\leq i\leq k}$ for each $k$. 
In an opposite direction, we recall that the $t_g$-recurrence is only a ``shadow'' of the fact that the generating functions of maps satisfy a set of infinitely many partial differential equations called the KP hierarchy.
 It is natural to expect that other joint moments of the variables $\YY_g^{(i:k)}$, apart from the two cases we have been able to track, are related to these equations. This may lead to a way, based on integrable hierarchies, of approaching \cref{conjecture}.

\smallskip

\noindent{\bf On this extended abstract.} This version is an extended abstract of a full paper available at arXiv:\href{https://arxiv.org/abs/1603.07714}{1603.07714}, to which we refer for full proofs. Here we skip most of the technical probabilistic details related to convergence (replaced here by heuristic considerations) and focus on the combinatorial techniques and on the path of proof which consists mostly in a conjoint use of generating functions and combinatorial bijections.

\section{Proof sketch of our main observation (\cref{thm:obs1})}

\subsection{Preliminaries}

For $g\geq 0$ we let $Q_g(z)$ be the generating function of rooted bipartite quadrangulations of genus $g$ by the number of faces, and we let $Q_g^\bullet(z)$ be the g.f.\ of the same objects where an additional vertex is pointed. We let $m_g(n) = [z^n] Q_g(z)$ and we use the same notation with $~^\bullet$. In what follows the notation $a(n)\sim b(n)$ means (as usual) that $a(n)/b(n)\rightarrow 1$ when $n$ tends to infinity, while the notation $F(z)\sim G(z) $ means that both $F$ and $G$ are algebraic functions of radius of convergence $\tfrac{1}{12}$, both have a unique dominant singularity at $z=\tfrac{1}{12}$, and we have $F(z)= G(z) (1+o(1))$ when $z\rightarrow \tfrac{1}{12}$ uniformly in a 
neighbourhood of $z=\tfrac{1}{12}$ slit along the line $[\tfrac{1}{12}, \infty)$. 

From \cite{BC0} (see also~\cite{CMS} for purely combinatorial proofs) we have for fixed $g\geq 0$:
$$
m_g(n) \sim t_g n^{\frac{5g-5}{2}} 12^n
\ \ , \ \ 
m^\bullet_g(n) 
= (n+2-2g) m_g(n) \sim t_g n^{\frac{5g-3}{2}} 12^n
$$\vspace{-8mm}
\begin{eqnarray}\label{eq:singQg}
Q^\bullet_g(z) \sim \Gamma(\tfrac{5g-1}{2}) t_g (1-12z)^{\frac{1-5g}{2}}
=
2^{2-5g}\tau_{g}
(1-12z)^{\frac{1-5g}{2}}
.
\end{eqnarray}


A \emph{labelled map} of genus $g$ is a rooted map $M$ of genus $g$ equipped with a function $\ell: V(M)\rightarrow \mathbb{Z}$ such that for any edge $(u,v)$ of $M$ one has $\ell(u)-\ell(v)\in \{-1,0,1\}$. We consider these objects up to global translation of labels (one can fix a translation class by fixing the label of some vertex to $0$).
A \emph{labelled one-face map (l.1.f.m.)} is a labelled map having only one face. We let $\mathcal{L}_n^{(g)}$ be the set of (rooted) l.1.f.m.\ of genus $g$ with $n$ edges.

The Marcus-Schaeffer bijection (\cite{MS}, see also~\cite{CMS}) is an explicit bijection
from
$
\mathcal{Q}_n^{(g)\bullet}$ to  $\{\uparrow,\downarrow\} \times \mathcal{L}_n^{(g)},
$
where $\mathcal{Q}_n^{(g)\bullet}$ is the set of rooted bipartite quadrangulations of genus $g$ and $n$ faces  equipped with a pointed vertex.
It follows that $Q^\bullet_g(z)=2L_g(z)$ where $L_g(z)$ is the generating function  of rooted l.1.f.m.\ of genus $g$ by the number of edges.
Moreover, in genus $0$, rooted one-face maps are trees, and a standard root-edge decomposition leads to the quadratic equation
$
L_0(z)= 1+3zL_0(z)^2,
$
from which we get the explicit formula:
\begin{eqnarray}\label{eq:valKernel}
 1-6zL_0(z) = \sqrt{1-12z}.
\end{eqnarray}

\subsection{Decomposition equation, Miermont's bijection, proof of \cref{thm:obs1}}


\begin{figure}
\begin{center}
\includegraphics[width=\linewidth]{decomp2.pdf}
\caption{Illustration of the decomposition leading to \eqref{eq:Tutte}}\label{fig:Tutte}
\end{center}
	\vspace{-0.5cm}
\end{figure}



We now come to the substance of this work, which is simply to try to write an equation for the generating function of l.1.f.m.\ by root-edge decomposition, and see what happens. We fix $g\geq 0$, and we consider a l.1.f.m.\ $M$ of genus $g+1$. If we remove the root edge of this map, two things can happen (see \cref{fig:Tutte}):
\begin{itemize}[itemsep=0pt, topsep=0pt,parsep=0pt, leftmargin=20pt]
\item[(i)] we disconnect the map into two l.1.f.m.\ $M_1$ and $M_2$ whose genera sum up to $g+1$;
\item[(ii)] we do not disconnect the map; in this case we are left with a map $M'$ of genus $g$ with two faces. Each face of $M'$ carries a distinguished corner, and the labels of these two corners differ by $-1$, $0$, or $1$.
\end{itemize}

\noindent 
Translating this operation  into an equation for generating functions we obtain
\begin{eqnarray}\label{eq:Tutte}
L_{g+1}(z) 
= 
3z\sum_{g_1+g_2=g+1\atop g_1,g_2\geq 0}
L_{g_1}(z) 
L_{g_2}(z) 
+
z A_g(z)
\end{eqnarray}
where:\vspace{-5mm}
\begin{itemize}[itemsep=0pt, topsep=0pt, parsep=0pt, leftmargin=60pt]
\item[-]
 in the first term the factor $3z$ takes into account the choice of the increment of label along the root-edge in $\{-1,0,1\}$;
\item[-]  $A_g(z)$ is the generating function by the number of edges, of unrooted labelled two-face maps, with faces numbered $F_1,F_2$, such that the face $F_i$ contains a marked corner $c_i$ for $i=1..2$, and that $|\ell(c_1)-\ell(c_2)|\leq 1$.
\end{itemize}

\noindent Objects counted by $A_g(z)$ can be related to quadrangulations thanks to Miermont's bijection~\cite{Miermont:tessellations}. This bijection is a generalization of the Marcus-Schaeffer bijection where the l.1.f.m is replaced by a labelled map having an arbitrary number, say $K$, of faces. We will apply it for $K=2$. 
In the following discussion, where we assume some familiarity with Miermont's bijection, we will show  how to arrive informally at \cref{lemma:convergenceCell} below, and why this implies \cref{thm:obs1}. As we said we will focus on key combinatorial features and stay at the intuitive level for  technical probabilistic facts.

Let us consider an object counted by $[z^n] A_g(z)$. Let us fix the translation class of the labels by saying that the minimum label in face $F_1$ is zero, and let us call $\delta$ the minimum label in face $F_2$. Let $i_1\geq 0$ and $i_2\geq \delta$ be the labels of the two marked corners $c_1$ and $c_2$,  respectively, and recall that $i_1-i_2\in \{-1,0,1\}$.
 Applying Miermont's bijection~\cite{Miermont:tessellations} to this object, we construct a bipartite quadrangulation $Q$ of genus $g$ by adding a new vertex $s_1, s_2$ inside each face $F_1, F_2$, and applying a certain closure operation. At the end of the construction, we obtain a quadrangulation such that  $d(s_1,s_2)+\delta$ is even. Moreover, the two corners $c_1$ and $c_2$ of the original two-face map are naturally associated to two edges $e_1$ and $e_2$ of the quadrangulation, and the construction is such that if $m_i$ is the endpoint of $e_i$ closer from $s_i$ in $Q$, for $i\in \{1,2\}$ one has: 
$$
d(s_1,m_1)=i_1 \ \ ,\ \ d(s_2,m_2)=i_2-\delta \ \ , \ \ 
d(s_2,m_1)\geq i_1-\delta \ \ ,\ \ d(s_1,m_2)\geq i_2.$$
These constraints can simply be rewritten as:
\begin{align}\label{eq:crossed}
d(s_1,m_1) \leq d(s_1,m_2) -\epsilon\ \ , \ \ 
d(s_2,m_2) \leq d(s_2,m_1) -\epsilon,
\end{align}
where $\epsilon = i_2-i_1$ is such that $|\epsilon|\leq 1$.
Loosely speaking, the properties in~\eqref{eq:crossed} say that, \emph{up to an error at most 1}, $s_i$ is (weakly) closer to $m_i$ than to $m_{3-i}$ for $i=1..2$. 
 Unfortunately these constraints do not entirely characterize these objects (see~\cite[Sec~2.2]{Miermont:tessellations}) but they do, in some sense, asymptotically\footnote{Roughly speaking the only ambiguity comes from vertices where an equality is reached in~\eqref{eq:crossed}, but these are in negligible proportion with high probability.}. Thinking heuristically for a moment, we can expect that the analogue in the continuum limit of these discrete configurations is a Brownian map with four marked points $(m_1^\infty, m_2^\infty, s_1^\infty, s_2^\infty)$ such that if we subdivide the space in two nearest-neighbour cells induced by  $m_1^\infty$ and $m_2^\infty$, the point $s_i^\infty$ belongs to the nearest-neighbour cell induced by $m_i^\infty$ for each $i=1..2$.
Up to technical details that we will carry out in the next section, this leads us quite naturally to the following conclusion:
\begin{lemma}\label{lemma:convergenceCell}
The coefficient $[z^n]A_g(z)$ is such that, as $n$ tends to $\infty$, with the notation of \cref{thm:obs1}:
\begin{eqnarray}\label{eq:convergenceCell}
\frac{[z^n]A_g(z)}{3/2 \cdot n^3m_{g}(n)} \longrightarrow \mathbf{E}[\XX_g(1-\XX_g)]
\end{eqnarray}
\end{lemma}
\begin{rem}\label{rem:1} The reader can understand heuristically the meaning of the denominator $3/2 \cdot n^3 m_{g}(n)$ as follows. The tuple $(Q,s_1,s_2,e_1,e_2)$ is a quadrangulation with two vertices and two marked edges. We can use $e_1$ as the root-edge of $Q$, and orient it by deciding that its source is at even distance from~$s_1$. We can choose the ``error'' $\epsilon$ freely in $\{-1,0,1\}$ (since asymptotically we do not expect this error to play any role), and set $i_1:=d(s_1,m_1)$ and $\delta:=i_1+\epsilon - d(s_2,m_2)$. Since Miermont's bijection requires that $d(s_1,s_2)+\delta$ is even, we are left with a rooted quadrangulation with one marked edge~$e_2$, and two marked vertices $(s_1,s_2)$ subject to \emph{two} parity constraints (that $s_1$ is at even distance from the root, and that $d(s_1,s_2)+\delta$ is even). Since a quadrangulation with $n$ faces has $2n$ edges and $n+2-2g$ vertices, and since it is natural to expect each parity constraint to contribute an asymptotic factor $\frac{1}{2}$, the total number of ``base configurations'' we obtain is $\sim 3\times (2n) n^2/4 \cdot m_g(n)$, hence the denominator in~\eqref{eq:convergenceCell}. 
\end{rem}


We  now conclude the proof of \cref{thm:obs1}.  The main idea is to express in two ways the "unknown" series $A_g(z)$ (at leading order). First, rewrite the decomposition~\eqref{eq:Tutte} as:
\begin{eqnarray}\label{eq:TutteKernel}
(1-6zL_0(z)) L_{g+1}(z) 
- 
3z\sum_{g_1+g_2=g+1,\atop g_1,g_2>0}
L_{g_1}(z) 
L_{g_2}(z) 
=
z A_g(z),
\end{eqnarray}
which expresses the generating function $L_{g+1}(z)$ in terms of the lower genus functions $L_i(z)$ for $i=1..g$, and of the ``unknown'' quantity $A_g(z)$.
We recall that $Q^\bullet_g(z)=2L_g(z)$ and~\eqref{eq:singQg}, from which we observe that each term in the left side of~\eqref{eq:TutteKernel} has a dominant singularity at $z=\tfrac{1}{12}$ with the same order of magnitude. More precisely, for the first term, using~\eqref{eq:valKernel}, we obtain $(1-6zL_0(z))L_{g+1}(z)\sim 2^{1-5(g+1)}\tau_{g+1}(1-12z)^{1-\frac{5}{2}(g+1)}$.
For product terms we have 
$L_{g_1}(z) L_{g_2}(z)\sim
2^{2-5(g+1)}\tau_{g_1}\tau_{g_2}(1-12z)^{1-\frac{5}{2}(g_1+g_2)}$.
It follows, using standard transfer theorems for algebraic functions~\cite{Flajolet} that when $n$ tends to infinity:
\begin{eqnarray}
[z^{n-1}] A_g(z) \sim 12^n n^{\frac{5g+1}{2}} 
2^{1-5(g+1)}\Gamma\left(\tfrac{5g+3}{2}\right)^{-1}
\big(\tau_{g+1} - \tfrac{1}{2}\sum_{g_1+g_2=g+1\atop g_1,g_2>0} \tau_{g_1}\tau_{g_2} \big).
\end{eqnarray}
But \cref{lemma:convergenceCell} gives another expansion of the ``unknown'' coefficient $[z^{n-1}] A_g(z)$, namely:
{\small
$$
[z^{n-1}] A_g(z) =\mathbf{E}\XX_g(1-\XX_g) \cdot 3/2\cdot n^3 m_{g}(n-1) 
\sim\mathbf{E}\XX_g(1-\XX_g)\cdot  3\cdot 2^{1-5g}\Gamma(\tfrac{5g-1}{2})^{-1} \tau_g n^{\frac{5g+1}{2}} 12^{n-1}.
$$
}
\cref{thm:obs1} follows by comparing the last two expansions of the ``unknown'' quantity $[z^{n-1}]A_g(z)$.


\section{Three marked points (proof of \cref{thm:3points})}

We  will now use our remaining space to sketch the proof of \cref{thm:3points}. We will be even quicker than in the previous section only giving an idea of why the third moment of \cref{thm:3points} shows up in the argument. We refer again to the arxiv version for full details.

We first need some definitions from~\cite{CMS, Chapuy:trisections}. If $L$ is a one-face map, its \emph{skeleton} is the map obtained by removing all vertices of degree~$1$ in $L$, and continuing to do so recursively until only vertices of degree at least $2$ remain. 
Vertices of a one-face map that are vertices of degree at least $3$ of its skeleton are called \emph{nodes}. A node $v$ that has degree $k$ in the skeleton is called a $k$-node (note that its degree as a vertex in the one-face map can be larger than $k$). A one-face map is \emph{dominant} if all vertices of its skeleton have degree at most $3$, \textit{i.e.} if all its nodes are $3$-nodes. It is proved in \cite{CMS} that for fixed $g$, as $n$ tends to infinity, a proportion at least $1-O(n^{-1/4})$ of l.1.f.m.\ of genus $g$ with $n$ edges are dominant.
By Euler's formula, a dominant one-face map has $4g-2$ nodes.


Following~\cite{Chapuy:trisections}, we introduce the operation of \emph{opening}. If $L$ is a one-face map and $v$ is a $3$-node of $L$, the \emph{opening} of $v$ is the operation that consists in replacing $v$ by three new vertices, each linked to one edge of the skeleton, and distributing the three (possibly empty) subtrees attached to $v$ among these new vertices as in the following figure:
\begin{center}\includegraphics[width=0.4\linewidth]{opening.pdf}\end{center}
Following~\cite{Chapuy:trisections},
we distinguish two types of $3$-nodes in a one-face map: \emph{intertwined nodes}, which are such that their opening results in a one-face map of genus $g-1$ with three marked vertices; and \emph{non-intertwined nodes}, which are such that their opening results in a map of genus $g-2$ with three faces, and one marked vertex inside each face (here the map can be disconnected, and its genus and number of faces are defined additively on connected components). The \emph{trisection lemma}~\cite[Lemma~5]{Chapuy:trisections}, which is the key result underlying this section, asserts that any dominant map of genus $g\geq 1$ has exactly $2g$ intertwined nodes, hence $2g-2$ non-intertwined ones.

It follows that the number $K_{g+2}(n)$ of l.1.f.m.\ of genus $g+2$ with $n$ edges whose root edge is a skeleton-edge leaving a \emph{non-intertwined} $3$-node satisfies:
\begin{eqnarray}\label{eq:doubleRooting}
K_{g+2}(n)\sim\frac{6(g+1)}{2n} [z^n] L_{g+2}(z).
\end{eqnarray}
Indeed, the first-order contribution is given by dominant l.1.f.m., and in a dominant l.1.f.m.\ of genus $g+2$ we can choose $3(2(g+2)-2)=6(g+1)$ edges outgoing from a non-intertwined node as a new root edge, but we obtain each map $2n$ times in this way (since maps counted by $L_{g+2}(z)$ are already rooted at one of their $2n$ oriented edges). 


We are now going to obtain another expression for the number $K_{g+2}(n)$ by performing a combinatorial decomposition. Comparing the two will lead us to \cref{thm:3points}.
Let $L$ be a dominant l.1.f.m of genus $g+2$ whose root edge is a skeleton-edge leaving a non-intertwined $3$-node $v$. We distinguish three cases, according to what happens when we perform the opening of the node $v$ (see \cref{fig:Tutte3}):
\begin{itemize}[itemsep=0pt, topsep=0pt,parsep=0pt, leftmargin=30pt]
\item[(i)] we disconnect the map into three components;
\item[(ii)] we disconnect the map into two components; 
\item[(iii)] we do not disconnect the map.
\end{itemize}
\begin{figure}
\begin{center}
\includegraphics[width=\linewidth]{decomp3.pdf}
\caption{The three cases for a one-face map of genus $g+2$ rooted at skeleton edge leaving a non-intertwined $3$-node $v$.}\label{fig:Tutte3}
\end{center}
	\vspace{-1cm}
\end{figure}





It should be no surprise to our experienced reader that the generating functions for the first two cases (which we denote by  $C_{g+2}^{(i)}(z)$ and $C_{g+2}^{(ii)}(z)$) can be expressed in terms of generating functions of maps rooted in several ways.
Filling in the details, one easily sees that the leading-order contribution for the sum of the first two cases is:
\begin{equation}\label{eq:1+2}
C_{g+2}^{(i)}(z) + C_{g+2}^{(ii)} (z) \sim 2^{-5(g+2)+1} \left(
3\cdot\!\! 
\sum_{\scriptscriptstyle g_1+g_2\atop=g+2} \!\!\!\tau_{g_1}\tau_{g_2} 
-\!\!\!
\sum_{\scriptscriptstyle g_1+g_2+g_3\atop =g+2} \!\!\!\!\tau_{g_1}\tau_{g_2} \tau_{g_3}
\right)
\cdot (1-12z)^{\frac{3}{2}-\frac{5}{2}(g+2)}
\end{equation}
where the sums are taken over positive indices ({\it i.e.} $g_1,g_2,g_3 >0$). Observe the \emph{cubic} convolution (triple sum), that naturally reflects the fact that the removal of the marked node in case (i) disconnects the map into three components.


We now study case (iii) and for this,
we apply again the Miermont's bijection. If we disconnect the three endpoints belonging to the skeleton and the root vertex in a map from case (iii), we obtain a labelled map of genus $g$ with three faces, with one marked vertex inside each face, subject to the constraint that those three vertices have the same label (see \cref{fig:Tutte3}-Right). Miermont's bijection transforms this object into a bipartite quadrangulation of genus $g$ with \emph{six} marked vertices $(s_1,s_2,s_3,v_1,v_2,v_3)$, such that for $i=1..3$ the source $v_i$ is closer from the vertex $s_i$ than from the two other vertices $s_j$ (to see this, write precisely the inequalities analogue to~\eqref{eq:crossed} in previous section). As in the previous section, up to subdominating cases, this property  asymptotically characterizes those configurations, and we get:
\begin{lemma}\label{combiToMoment3points}
The number $c_{g+2}^{(iii)}(n)$ of configurations in case (iii) satisfies:
$$
\frac{c_{g+2}^{(iii)}(n)}{n^5/4 \cdot 2^{-2} m_g(n)} \sim \mathbf{E}[\YY_g^{(1:3)}\YY_g^{(2:3)}\YY_g^{(3:3)}].
$$
\end{lemma}
\noindent The reader can understand heuristically the denominator in the previous expression as follows. The factor $n^5/4$ comes from the fact that we have $\sim n^6$ ways to mark 6 vertices (among $n+2-2g$) but the quadrangulation is unrooted so  we divide by $4n$. The factor $2^{-2}$ corresponds to the fact that we have two parity constraints relating the distances of the six points together (these constraints enable us to choose the delays in such a way that the target vertices get the same label while respecting the parity constraints on delays required by Miermont's bijection). Now that we have seen how to make the quantity $\mathbf{E}[\YY_g^{(1:3)}\YY_g^{(2:3)}\YY_g^{(3:3)}]$ appear, let us sketch the end of the proof.

\smallskip
{\bf Sketch of the path to the proof of \cref{thm:3points}.} Summing contributions given by the last lemma and by \eqref{eq:1+2} enables us to obtain an expression of the leading order of the sum of the three cases $(i)$, $(ii)$, $(iii)$, therefore to obtain an alternative expression for the quantity \eqref{eq:doubleRooting}, at leading order. Comparing the two, we therefore obtain an expression of $ \mathbf{E}[\YY_g^{(1:3)}\YY_g^{(2:3)}\YY_g^{(3:3)}]$ as a \emph{trilinear} expression in the $(t_h)_{h\leq g+2}$.
So far, we have not used the $t_g$-recurrence. We will do it now, and a miracle happens. By doing a suitable bootstrap of the $t_g$-recurrence, we can obtain a (complicated) trilinear relation satisfied by the numbers $(t_g)_{g\geq 0}$. It turns out that this trilinear recurrence (which is equivalent to the $t_g$-recurrence) enables us to simplify considerably the obtained expression.
Indeed, as was the case in the previous section for the case of two points, the algebra works perfectly and after simplifications, one obtains that $\mathbf{E}[\YY_g^{(1:3)}\YY_g^{(2:3)}\YY_g^{(3:3)}]$ is in fact equal to $1/60$. We do not have any explanation for this remarkable simplification, and refer the reader to the full version for details of the tedious computations.

\section*{Conclusion}
We could be disappointed by the seemingly ``magical'' simplification that occurs at the very end of the proof. Instead, we believe that the fact that computations match so well is just a shadow of the deep links between combinatorial bijections, random maps, and integrable hierarchies. Our results strongly suggest that a unified understanding of these links is possible, although much remains to be done. We hope that \cref{conjecture} can play a stimulating role in this direction.

\begingroup\emergencystretch=2em
\printbibliography
\endgroup



\end{document}
